import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;

public class MazeSolver {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右, 下, 左, 上
    private static final int WALL = 0;
    private static final int UNEXPLORED = -1;
    private static final int PATH = 2;

    public static void solveMaze(int[][] maze, int startX, int startY, int endX, int endY) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startX, startY});
        maze[startX][startY] = PATH;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            if (cell[0] == endX && cell[1] == endY) {
                System.out.println("Maze solved!");
                return;
            }

            for (int[] direction : DIRECTIONS) {
                int nextX = cell[0] + direction[0];
                int nextY = cell[1] + direction[1];
                if (isValidCell(maze, nextX, nextY)) {
                    maze[nextX][nextY] = PATH;
                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }
        System.out.println("No path found.");
    }

    private static boolean isValidCell(int[][] maze, int x, int y) {
        return x >= 0 && x < maze.length && y >= 0 && y < maze[x].length && maze[x][y] == UNEXPLORED;
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 0, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 1, 0, 1, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0}
        };

        solveMaze(maze, 0, 0, 4, 4);
        System.out.println("Maze:");
        for (int[] row : maze) {
            System.out.println(Arrays.toString(row));
        }
    }
}
